后缀自动机

后缀自动机 Suffix Automaton


概念

一个串 $s$ 的后缀自动机(SAM)是一个有限状态自动机(DFA),它能且只能接受所有 $s$ 的后缀,并且拥有最少的状态与转移。

定义

1、后缀自动机母串为 $s$ ,令 $s[l,r]$ 表示 $s$ 中第 $l$ 个字符到第 $r$ 个字符组成的字符串。
2、第 $i$ 个位置开始的后缀为 $suf_{i}$ ,到第 $i$ 个位置为止的前缀为 $pref_{i}$。
3、$SAM_{str}$ 表示从初始状态读入字符串 $str$ 后的状态。
4、对于一个串 $s$ 的一个子串 $str$ ,令 $right_{str}$ 表示 $str$ 在 $s$ 中每一次出现的右端点位置组成的集合。

  • 对于 $right$ 的理解
    1、考虑一个串 $str$ ,如果 $str$ 是 $s$ 的一个子串,那么 $SAM_{str}$ 一定是个合法状态。因为可以在 $str$ 后添加若干字符来变成 $s$ 的一个后缀,即每一个子串在sam中都有对应状态。
    2、考虑 $s$ 的一个子串,如果 $right_{str}$ 和 $right_{a+str}$ ( $a$ 是一个字符串) 完全一致的话,就可以把它们合并为同一状态。因为从这两个字符串开始添加字符,能够得到的后缀是一样的。因此这两个串在sam中的本质是一样的,可以合并。
    3、考虑 $s$ 的两个子串 $A,B$ 。如果 $right_{A}$ 和 $right_{B}$ 有交,那么显然有一个串是另一个串的后缀,这里不妨设 $A$ 是 $B$ 的后缀,那么 $right_{B} \subset right_{A}$,也就是说,对于 $s$ 的任意两个子串,它们的 $right$ 集合要么没有交集,要么一个包含另一个。

5、令一个状态 $s$ 的父状态 $fa_{s}$ 为满足 $right_{s} \subset right_{fa}$ ,且 $\mid right_{fa} \mid$最小的状态。那么所有状态会形成一个树结构,叫 $parent$ 树。

  • 例如字符串 $abcbc$ ,右图为对应 $parent$ 树
    sam1

构造方法(增量法)

对于每个状态 $s$ ,记它代表的最长子串的长度为 $len_{s}$ 。
考虑当前已经有前 $\mid s \mid$-1个字符的sam,且现在的自动机中 $[1,\mid s \mid-1]$ 位于状态 $last$ 。现在加入第 $\mid s \mid$个字符 $c$ ,我们新建一个状态 $np$ ,显然 $len_{np}=\mid s \mid$ 。
考虑转移,显然应该有 $last \to np$ 的转移,然后是 $fa_{last} \to np$ 的转移,通过 $fa$ 一直向上传递,直到发现有一个状态有该转移,将该状态记为 $p$ ,转移到状态 $q$ 。
此时状态 $q$ 中会增加右端点为 $\mid s \mid$,且最长长度为 $len_{p}+1$ 的串。
考虑如何维护,不妨分为两种情况:
1、$len_{q}=len_{p}+1$ ,此时状态 $q$ 中所有串的 $right$ 仍然相同,只需令 $fa_{np}=q$ ;
2、$len_{q}>len_{p}+1$ ,此时状态 $q$ 中长度小于等于 $len_{p}+1$ 的串的 $right$ 发生变化,我们要把这一部分提出来。新建一个状态 $nq$ ,将 $q$ 的转移和 $fa$ 赋给 $nq$ ,同时令 $fa_{q}=fa_{np}=nq$ ,并将能转移到 $q$ 的改为转移到 $nq$ 。
代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert(int w){
int p=last,np=init(len[last]+1);
last=np;
for(;p&&!ch[p][w];p=fa[p])ch[p][w]=np;
if(!p)fa[np]=rt;
else{
int q=ch[p][w];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=init(len[p]+1);
for(int i=0;i<26;i++)ch[nq][i]=ch[q][i];
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
for(;p&&ch[p][w]==q;p=fa[p])ch[p][w]=nq;
}
}
}

性质

1、每个状态 $s$ 所代表的串的长度为 $(len_{fa_{s}} , len_{s}]$ 。
2、每个状态 $s$ 所代表的所有串在原串中出现次数及出现的右端点相同。
3、在 $parent$ 树中,每个状态的 $right$ 集合是它的父状态 $right$ 集合的子集。
4、两个串的最长公共后缀,位于两个串对应的状态在 $parent$ 树上的 $LCA$ 。

  • 仍然是字符串 $abcbc$ , $parent$ 树每个节点旁依次为出现次数,长度区间,所代表的字符串
    sam2
0%